<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        var minimumTimeRequired = function (jobs, k) {
            // 记录每个工人的工作时间
            var record = new Array(k).fill(0);
            var min = Infinity;

            function backtrack(index) {
                // 得到一种分配方式，更新最优解
                if (index >= jobs.length) {
                    min = Math.min(min, Math.max(...record));
                    return;
                }

                var cache = {};
                // 尝试将工作分配给不同的工人
                for (var i = 0; i < record.length; i++) {
                    // 剪枝，因为还在循环里，说明工人够用，可以直接分配给当前工人，相当于当前工人和上一次分配到这个时间的工人一样
                    // 相同工作时间不需要再次尝试
                    var n = record[i];
                    if (cache[n]) continue;
                    cache[n] = 1;

                    // 剪枝，工作时间超过了当前的最优解
                    if (record[i] + jobs[index] > min) continue;

                    // 改变状态
                    record[i] += jobs[index];

                    // 递归
                    backtrack(index + 1);

                    // 回溯，还原状态
                    record[i] -= jobs[index];
                }
                console.log(record)
            }

            backtrack(0);
            return min;
        };
        console.log(minimumTimeRequired([3,2,3], 3))
    </script>
</body>

</html>